﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace WindowsFormsApplication1
{
    class AntSystem
    {
        public int MAX_ANTS;
        int alpha = 2;
        int betha = 3;
        double RHO = 0.6;
        double INITIAL_PHEROMONE;

        int curTime;
        double elapsedTime;
        Ant[] ants;
        double bestSoFar;
        double worstSoFar;
        double bestPosible;
        double worstPosible;
        int bestIndex;
        int wourstIndex;
        int QVAL;
        public bool problemSolved;
        double[,] pheromone_;
        int[] solution_;
        TSP.DataFromFile data_;
        int maxIterations_;
        int iteration_;

        public AntSystem(TSP.DataFromFile data, int[] solution, int startMaxCount, double[,] pheromone)
        {
            pheromone_ = pheromone;
            iteration_ = 0;
            maxIterations_ = startMaxCount;
            solution_ = solution;
            MAX_ANTS = 25;
            data_ = data;
            FixZeroDistances();
            QVAL = 100;
            INITIAL_PHEROMONE = 1.0 / data_.dimension;
            bestSoFar = int.MaxValue;
            worstSoFar = 0;
            bestPosible = int.MaxValue;
            worstPosible = 0;
            problemSolved = false;
            ants = new Ant[MAX_ANTS];
            for (int i = 0; i < MAX_ANTS; ++i)
            {
                ants[i] = new Ant(data_.dimension);
            }

            //pheromone_ = new double[data_.dimension, data_.dimension];
            for (int i = 0; i < data_.dimension; ++i)
            {
                for (int j = 0; j < data_.dimension; ++j)
                {
                    pheromone_[i, j] = INITIAL_PHEROMONE;
                }
            }
            int to = 0;
            for (int ant = 0; ant < MAX_ANTS; ++ant)
            {
                if (to == data_.dimension)
                    to = 0;

                ants[ant].currentCity_ = to++;
                for (int from = 0; from < data_.dimension; ++from)
                {
                    ants[ant].visitedCities_[from] = 0;
                    ants[ant].path_[from] = -1;
                }

                ants[ant].pathIndex = 1;
                ants[ant].path_[0] = ants[ant].currentCity_;
                ants[ant].nextCity_ = -1;
                ants[ant].tourLength_ = 0.0;
                ants[ant].visitedCities_[ants[ant].currentCity_] = 1;
            }
        }

        public void FixZeroDistances()
        {
            for (int i = 0; i < data_.dimension; ++i)
            {
                for (int j = 0; j < data_.dimension; ++j)
                {
                    if (data_.matrix[i, j] == 0)
                    {
                        data_.matrix[i, j] = 0.0000001;
                    }
                }
            }
        }

        public void RestartAntSystem()
        {
            int ant, i, to = 0 ;

            Random rand = new Random();

            for (ant = 0; ant < MAX_ANTS; ++ant)
            {
                if ((ants[ant].tourLength_ < bestSoFar) && (ants[ant].tourLength_ > 0))
                {
                    bestSoFar = ants[ant].tourLength_;
                    bestIndex = ant;
                    for (int k = 0; k < data_.dimension; ++k)
                    {
                        solution_[k] = ants[ant].path_[k];
                    }
                }

                if (ants[ant].tourLength_ > worstSoFar)
                {
                    worstSoFar = ants[ant].tourLength_;
                    wourstIndex = ant;
                }

                
                problemSolved = (iteration_ > maxIterations_);

                ants[ant].nextCity_ = -1;
                ants[ant].tourLength_ = 0;

                for (i = 0; i < data_.dimension; ++i)
                {
                    ants[ant].visitedCities_[i] = 0;
                    ants[ant].path_[i] = -1;
                }

                if (to == data_.dimension) to = 0;

                ants[ant].currentCity_ = rand.Next(data_.dimension);
                ants[ant].pathIndex = 1;
                ants[ant].path_[0] = ants[ant].currentCity_;
                ants[ant].visitedCities_[ants[ant].currentCity_] = 1;
            }
        }

        public double AntProduct(int from, int to)
        {
            return Math.Pow(pheromone_[from, to], alpha) * Math.Pow(1.0 / data_.matrix[from, to], betha);
        }

        public int GetNextCity(int ant)
        {
            int from, to;
            double denom = 0;
            from = ants[ant].currentCity_;
            for (to = 0; to < data_.dimension; to++)
            {
                if (ants[ant].visitedCities_[to] == 0)
                {
                    denom += AntProduct(from, to);
                }
            }

            //do
            //{
            //    double p;

            //    to++;
            //    if (to >= data_.dimension) to = 0;
            //    if (ants[ant].visitedCities_[to] == 0)
            //    {
            //        p = AntProduct(from, to) / denom;
            //        Random rand = new Random();
            //        if (rand.NextDouble() < p)
            //            break;
            //    }
            //} while (true);
            //double[] probabilities = new double[data_.dimension];

            double maxProb = 0;
            to = -1;
            for (int i = 0; i < data_.dimension; ++i)
            {
                if (ants[ant].visitedCities_[i] == 0)
                {
                    double temp = AntProduct(from, i) / denom;
                    if (maxProb < temp)
                    {
                        maxProb = temp;
                        to = i;
                    }
                }
            }

            return to;
        }

        public int SimulateAnts()
        {
            int k;
            int moving = 0;

            for (k = 0; k < MAX_ANTS; ++k)
            {
                if (ants[k].pathIndex < data_.dimension)
                {
                    ants[k].nextCity_ = GetNextCity(k);
                    ants[k].visitedCities_[ants[k].nextCity_] = 1;
                    ants[k].path_[ants[k].pathIndex++] = ants[k].nextCity_;
                    ants[k].tourLength_ += data_.matrix[ants[k].currentCity_, ants[k].nextCity_];

                    if (ants[k].pathIndex == data_.dimension)
                    {
                        ants[k].tourLength_ += data_.matrix[ants[k].path_[data_.dimension - 1], ants[k].path_[0]];
                    }
                    ants[k].currentCity_ = ants[k].nextCity_;
                    moving++;
                }
            }
            if (moving == 0)
            {
                ++iteration_;
            }
            return moving++;
        }

        public void UpdateTrails()
        {
            int from, to, i, ant;
            for (from = 0; from < data_.dimension; from++)
            {
                for (to = 0; to < data_.dimension; to++)
                {
                    if (from != to)
                    {
                        pheromone_[from, to] *= (1.0 - RHO);
                        if (pheromone_[from, to] < 0)
                            pheromone_[from, to] = 0;
                    }
                }
            }

            for (ant = 0; ant < MAX_ANTS; ant++)
            {
                for (i = 0; i < data_.dimension; ++i)
                {
                    if (i < data_.dimension - 1)
                    {
                        from = ants[ant].path_[i];
                        to = ants[ant].path_[i + 1];
                    }
                    else
                    {
                        from = ants[ant].path_[i];
                        to = ants[ant].path_[0];
                    }

                    pheromone_[from, to] += (QVAL / ants[ant].tourLength_);
                    pheromone_[to, from] = pheromone_[from, to];
                }
            }

            for (from = 0; from < data_.dimension; from++)
            {
                for (to = 0; to < data_.dimension; ++to)
                {
                    pheromone_[from, to] *= RHO;
                }
            }
        }


    }
}
